package com.leetcode.algorithm.y22.m09.w2;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * 815. 公交路线
 * 
 * https://leetcode.cn/problems/bus-routes/
 * 
 * @author jie.deng
 *
 */
class Question0815Solution01 {

	public int numBusesToDestination(int[][] routes, int source, int target) {
		if (source == target) {
			return 0;
		}
		Map<Integer, Set<Integer>> bus2Station = new HashMap<>();
		Map<Integer, Set<Integer>> station2Bus = new HashMap<>();
		for (int bus = 0; bus < routes.length; bus++) {
			Set<Integer> stationSet = new HashSet<>();
			for (int idx = 0; idx < routes[bus].length; idx++) {
				stationSet.add(routes[bus][idx]);
				Set<Integer> busSet = station2Bus.get(routes[bus][idx]);
				if (busSet == null) {
					busSet = new HashSet<>();
					station2Bus.put(routes[bus][idx], busSet);
				}
				busSet.add(bus);
			}
			bus2Station.put(bus, stationSet);
		}

		if (!station2Bus.containsKey(source) || !station2Bus.containsKey(target)) {
			return -1;
		}

		Set<Integer> visitedSet = new HashSet<>();
		Queue<Integer> queue = new LinkedList<>();
		int level = 0;
		visitedSet.add(source);
		queue.offer(source);
		while (!queue.isEmpty()) {
			int size = queue.size();
			level++;
			for (int i = 0; i < size; i++) {
				Integer stationIdx = queue.poll();
				Set<Integer> busSet = station2Bus.get(stationIdx);
				for (Integer bus : busSet) {
					Set<Integer> stationSet = bus2Station.get(bus);
					for (Integer station : stationSet) {
						if (station == target) {
							return level;
						}
						if (visitedSet.add(station)) {
							queue.add(station);
						}
					}
				}
			}
		}

		return -1;
	}

}